package com.base.string;

/**
 * @author leon
 * @Description: TODO
 * @date 2022年04月07日 16:24
 */
public class KMP {
    /**
     * 字符串匹配
     * @param s 匹配串
     * @param p 模式串
     * @return  第一个匹配的子串，模式串的第一个索引，-1表示没有匹配成功
     */
    public static  int strStr(String s,String p){
        if(p==null||p.length()==0){
            return 0;
        }
        if(s==null||s.length()==0){
            return -1;
        }
        if(s.length()<p.length()){
            return -1;
        }
        char[] ms = s.toCharArray();
        char[] ps = p.toCharArray();
        return kmp(ms,ps);
    }

    /**
     * KMP 算法
     * @param ms 匹配串
     * @param ps 模式串
     * @return 第一个匹配的子串，模式串的第一个索引，-1表示没有匹配成功
     */
    public static int kmp(char[] ms,char[] ps){
        int[] next = next(ps, ps.length);
        int j = 0;
        for (int i = 0; i < ms.length; i++) {
            while (j>0&&ms[i]!=ps[j]){
//                j = next[j]+1;
                j = next[j-1]+1;
                // 判断是否超出长度
                if(ps.length-j>ms.length-i){
                    return -1;
                }
            }
            // 如果两者相等，则模式串当前位后移一位
            if(ps[j] == ms[i]){
                j++;
            }
            // 整个模式串都遍历完了
            if(j == ps.length){
                return i-j+1;
            }
        }
        return -1;
    }

    /**
     * 求模式串的next数组
     * @param ps 模式串
     * @param n 串长
     * @return next数组
     */
    public static int[] getNext(char[] ps,int n){
        int[] next = new int[n];
        // 初始化，第一个字符不存在最长公共前后缀
        next[0] = 0;
        int k = 0;
        for (int i = 1; i < n; i++) {
            while (k>0&&ps[k]!=ps[i]){
                k = next[k];
            }
            if(ps[k] == ps[i]){
                ++k;
            }
            next[i] = k;
        }
        return next;
    }

    public static int[] next (char[] needle,int len) {
        //定义 next 数组
        int[] next = new int[len];
        // 初始化
        next[0] = -1;
        int k = -1;
        for (int i = 1; i < len; ++i) {
            //我们此时知道了 [0,i-1]的最长前后缀，但是k+1的指向的值和i不相同时，我们则需要回溯
            //因为 next[k]就时用来记录子串的最长公共前后缀的尾坐标（即长度）
            //就要找 k+1前一个元素在next数组里的值,即next[k]
            while (k != -1 && needle[k + 1] != needle[i]) {
                k = next[k];
            }
            // 相同情况，就是 k的下一位，和 i 相同时，此时我们已经知道 [0,i-1]的最长前后缀
            //然后 k - 1 又和 i 相同，最长前后缀加1，即可
            if (needle[k+1] == needle[i]) {
                ++k;
            }
            next[i] = k;

        }
        return next;
    }

    public static void main(String[] args) {
        String s = "abababca";
        int[] next1 = getNext(s.toCharArray(), s.length());
        int[] next2 = next(s.toCharArray(), s.length());

        System.out.println(strStr("mississippi", "issip"));
    }




}
